import java.util.ArrayList;
import java.util.Comparator;

public class BTree<Key, E> {
	private TreeNode<Key, E> root; // root of the tree
	private int nodecount; // number of nodes in the tree
	private Comparator<Key> c;

	BTree(Comparator<Key> c) {
		root = null;
		nodecount = 0;
		this.c = c;
	}

	public ArrayList<E> findAll(Key k) {
		return findAllhelp(root, k);
	}

	/**
	 * searches the BST for the element with key k
	 * 
	 * @param k
	 *            key of the element being searched for
	 * @return the element of the searched item
	 */
	public E find(Key k) {
		return findhelp(root, k);
	}

	/**
	 * inserts the element e with key k to a valid location in the tree
	 * 
	 * @param k
	 *            key of element being inserted
	 * @param e
	 *            element being inserted
	 */
	public void insert(Key k, E e) {
		root = inserthelp(root, k, e, false);
		nodecount++;
	}

	/**
	 * removes the given element. if none is found, null is returned
	 * 
	 * @param k
	 *            key of the removed element
	 * @return element of the removed node
	 */
	public E remove(Key k) {
		E temp = findhelp(root, k);
		if (temp != null) {
			root = removehelp(root, k);
			nodecount--;
		}
		return temp;
	}

	/**
	 * removes the node with the given key and coordinate
	 * 
	 * @param k
	 *            key of the removed element
	 */
	public void remove(Key k, E e) {
		root = removehelp(root, k, e);
		nodecount--;
	}

	/**
	 * inserts the given element to its right location in the tree
	 * 
	 * @param rt
	 *            root of subtree
	 * @param k
	 *            Key of element being inserted
	 * @param e
	 *            element being inserted
	 * @param flag
	 *            flag to check whether current node is equal to its parent node
	 * @return return the current subtree, modified to contain the new item
	 */
	private TreeNode<Key, E> inserthelp(TreeNode<Key, E> rt, Key k, E e,
			boolean flag) {
		if (flag) {
			TreeNode<Key, E> temp = new TreeNode<Key, E>(k, e);
			temp.setLeft(rt);
			return temp;
		} else {
			if (rt == null)
				return new TreeNode<Key, E>(k, e);
			if (c.compare(rt.key(), k) > 0)
				rt.setLeft(inserthelp(rt.left(), k, e, false));
			else if (c.compare(rt.key(), k) == 0)
				rt.setLeft(inserthelp(rt.left(), k, e, true));
			else
				rt.setRight(inserthelp(rt.right(), k, e, false));
			return rt;
		}
	}

	/**
	 * Remove a node with key value k
	 * 
	 * @param rt
	 *            root of subtree
	 * @param k
	 *            key of element being removed
	 * @return tree with node removed
	 */
	private TreeNode<Key, E> removehelp(TreeNode<Key, E> rt, Key k) {
		if (rt == null)
			return null;
		if (c.compare(rt.key(), k) > 0)
			rt.setLeft(removehelp(rt.left(), k));
		else if (c.compare(rt.key(), k) < 0)
			rt.setRight(removehelp(rt.right(), k));
		else // found the node
		{
			if (rt.left() == null)
				return rt.right();
			else if (rt.right() == null)
				return rt.left();
			else // two children
			{
				TreeNode<Key, E> temp = getmin(rt.right());
				rt.setElement(temp.element());
				rt.setKey(temp.key());
				rt.setRight(deletemin(rt.right()));
			}
		}
		return rt;
	}

	private TreeNode<Key, E> removehelp(TreeNode<Key, E> rt, Key k, E e) {
		if (rt == null)
			return null;
		if (c.compare(rt.key(), k) > 0)
			rt.setLeft(removehelp(rt.left(), k));
		else if (c.compare(rt.key(), k) < 0)
			rt.setRight(removehelp(rt.right(), k));
		else // found the node
		{
			if (rt.element() == e) {
				if (rt.left() == null)
					return rt.right();
				else if (rt.right() == null)
					return rt.left();
				else // two children
				{
					TreeNode<Key, E> temp = getmin(rt.right());
					rt.setElement(temp.element());
					rt.setKey(temp.key());
					rt.setRight(deletemin(rt.right()));
				}
			}
			else
			{
				removehelp(rt.left(), k, e);
			}
		}
		return rt;
	}

	private E findhelp(TreeNode<Key, E> rt, Key k) {
		if (rt == null)
			return null;
		if (c.compare(rt.key(), k) > 0)
			return findhelp(rt.left(), k);
		if (c.compare(rt.key(), k) == 0)
			return rt.element();
		else
			return findhelp(rt.right(), k);
	}

	/**
	 * helper method for the findAll method.
	 * 
	 * @param rt
	 *            root of the subtree being searched
	 * @param k
	 *            key of element
	 * @return element with given key k
	 */
	private ArrayList<E> findAllhelp(TreeNode<Key, E> rt, Key k) {
		if (rt == null)
			return null;
		if (c.compare(rt.key(), k) > 0)
			return findAllhelp(rt.left(), k);
		else if (c.compare(rt.key(), k) == 0) {
			return getEquals(rt, k);
		} else
			return findAllhelp(rt.right(), k);
	}

	private ArrayList<E> getEquals(TreeNode<Key, E> rt, Key k) {
		ArrayList<E> list = new ArrayList<E>();
		while (rt != null) {
			if (c.compare(rt.key(), k) == 0)
				list.add(rt.element());
			else
				break;
			rt = rt.left();
		}
		return list;
	}

	/**
	 * deletes the node with the minimum value.
	 * 
	 * @param rt
	 *            current subtree
	 * @return the current subtree with the minimum removed.
	 */
	private TreeNode<Key, E> deletemin(TreeNode<Key, E> rt) {
		if (rt.left() == null)
			return rt.right();
		rt.setLeft(deletemin(rt.left()));
		return rt;
	}

	/**
	 * finds and returns the minimum node of the subtree
	 * 
	 * @param rt
	 *            current subtree
	 * @return node with min value in the subtree
	 */
	private TreeNode<Key, E> getmin(TreeNode<Key, E> rt) {
		if (rt.left() == null)
			return rt;
		return getmin(rt.left());
	}
}
